<?php
/**
 * User: helloJiu
 * Date: 2021/10/14
 * Time: 11:12
 */

namespace App\Algorithm\DP;


class FindCheapestPriceByDP
{
    /**
     * 使用动态规划解决
     * https://labuladong.gitbook.io/algo/mu-lu-ye-2/mu-lu-ye-4/lv-hang-zui-duan-lu-jing
     * 787. K 站中转内最便宜的航班
     * https://leetcode-cn.com/problems/cheapest-flights-within-k-stops/
     * @param Integer $n
     * @param Integer[][] $flights
     * @param Integer $src
     * @param Integer $dst
     * @param Integer $k
     * @return Integer
     */
    function findCheapestPrice($n, $flights, $src, $dst, $k)
    {
        /**
         * 输入:
         * n = 3, edges = [[0,1,100],[1,2,100],[0,2,50]]
         * src = 0, dst = 2, k = 1
         * 输出: 200
         */
        $dp = [];
        // $dp[$i][$j] : 表示经过$i次到达$j的price
        for($i=0; $i<=$k; $i++){
            for($j=0; $j<$n; $j++){
                $dp[$i][$j] = PHP_INT_MAX;
            }
        }

        foreach($flights as $flight){
            if($flight[0] == $src){
                $dp[0][$flight[1]] = $flight[2];
            }
        }

        for($i=0; $i<=$k; $i++){
            $dp[$i][$src] = 0;
        }

        for($i=0; $i<=$k; $i++){
            foreach($flights as &$flight){
                $from = $flight[0];
                $to = $flight[1];
                $price = $flight[2];
                // [[0,1,4],[1,2,4],[0,3,2],[3,1,4],[1,4,5],[4,2,1]]
                // 每次迭代, 都会
                if(isset($dp[$i-1][$from]) && $dp[$i-1][$from] != PHP_INT_MAX){
                    if(isset($dp[$i][$to])){
                        $dp[$i][$to] = min($dp[$i-1][$from] + $price, $dp[$i][$to]);
                    }else{
                        $dp[$i][$to] = $dp[$i-1][$from] + $price;
                    }
                }
            }
        }
        print_r($dp);
        return $dp[$k][$dst] == PHP_INT_MAX ? -1 : $dp[$k][$dst];
    }


}